Étant donné une famille S de sous-ensembles d`un « univers » U, on cherche un sous-ensemble H de U (le hitting set) qui contient au moins un élément de chaque sous-ensemble de la famille S. De plus, il est demandé que le nombre d`éléments de H n`excède pas une valeur k donnée.